package com.fengdi.book.middle;


import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Stack;

public class OtherQuestions {
    public static class GetSum {
        public int getSum(int a, int b) {
            if(a == 0) return b;
            return getSum(a ^ b, (a & b) << 1);
        }
    }

    public static class EvalRPN {
        public int evalRPN(String[] tokens) {
            // 后缀表达式求值
            if(tokens == null || tokens.length == 0) return 0;
            Stack<Integer> numStack = new Stack<>();
            String regex = "-?\\d+";
            for(String token : tokens) {
                // 判断是否是数字，如果是，直接入栈
                if(token.matches(regex)) {
                    numStack.push(Integer.parseInt(token));
                }else { // 说明是运算符，需要从栈中取两个数字进行运算，然后将结果入栈
                    int temp = 0;
                    int x = numStack.pop();
                    int y = numStack.pop();
                    switch (token) {
                        case "+": temp = x + y; break;
                        case "-": temp = y - x; break;
                        case "*": temp = x * y; break;
                        case "/": temp = y / x; break;
                        default: break;
                    }
                    numStack.push(temp);
                }
            }
            return numStack.pop();
        }
    }

    public static class MajorityElement {
        public int majorityElement(int[] nums) {
            if (nums.length == 1) return nums[0];
            Arrays.sort(nums); // 排序
            int threshold = nums.length / 2;
            int temp = nums[0];
            int counter = 1;
            for(int i = 1; i < nums.length; i++) {
                if(temp == nums[i]) {
                    counter++;
                }else {
                    counter = 1;
                    temp = nums[i];
                }
                if(counter > threshold) return temp;
            }
            return -1;
        }
    }

    public static class LeastInterval {
        public int leastInterval(char[] tasks, int n) {
            if(n == 0) return tasks.length;
            LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
            for(char c : tasks) {
                if(map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                }else {
                    map.put(c, 1);
                }
            }

            int maxValue = this.getMax(map);
            // 判断是否有相同频率的任务
            int maxCount = 0;
            for(char k : map.keySet()) {
                if(map.get(k) == maxValue) {
                    maxCount++;
                }
            }
            return Math.max(((maxValue - 1) * (n + 1) + maxCount), tasks.length);
        }

        private int getMax(LinkedHashMap<Character, Integer> map) {
            int max = 0;
            for(Integer value : map.values()) {
                max = Math.max(max, value);
            }
            return max;
        }
    }


}
